package william.mergesort;

import william.utils.ArrayUtils;

import java.util.Arrays;

/**
 * @author ZhangShenao
 * @date 2024/1/23
 * @description 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArray(10, -100, 100);
        System.out.println("原始数组为: ");
        System.out.println(Arrays.toString(arr));
        mergeSortIteration(arr);
        System.out.println("排序后数组为: ");
        System.out.println(Arrays.toString(arr));
        System.out.println("数组是否按照升序排列: " + ArrayUtils.isInAscOrder(arr));
    }

    public static void mergeSort(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length < 2) {
            return;
        }

        //递归实现
        mergeSortRecursive(arr, 0, arr.length - 1);
    }

    /**
     * 递归实现
     * 对数组arr[L,R]范围进行归并排序
     */
    public static void mergeSortRecursive(int[] arr, int L, int R) {
        //递归终止条件
        if (L >= R) {
            return;
        }

        //找到数组中点
        int M = L + ((R - L) >> 1);

        //递归调用,保证数组左、右两部分分别有序
        mergeSortRecursive(arr, L, M);
        mergeSortRecursive(arr, M + 1, R);

        //将两个有序数组合并成一个整体有序的数组
        merge(arr, L, M, R);

    }

    /**
     * 迭代版本实现
     * 引入步长 step 的概念，step 初始=1。
     * 每轮迭代，从头开始遍历数组，找到左、右两组有序数组，每组的长度都为 step，并将两组有序数组合并成一个整体有序数组。寻找左右两组有序数组时，存在以下几种情况：
     * - 两组数组长度都 = step，正常合并即可。
     * - 左组长度 = step，右组长度 < step，也可以正常合并。
     * - 仅有左组，不存在右组，则无需进行合并。
     * 本轮处理完成后，step = step * 2，继续上述操作，直到 step >= 数组长度。
     */
    public static void mergeSortIteration(int[] arr) {
        //边界条件校验
        if (arr == null || arr.length < 2) {
            return;
        }

        //引入步长step的概念,step初始=1
        int step = 1;
        int len = arr.length;

        while (step < len) { //迭代终止条件: step >= len
            //每轮迭代,都从头开始寻找左、右两组数组
            int L = 0;

            while (L < len - 1) {
                //首先找到左组,范围[L,M]
                int M = L + step - 1;
                if (M >= len - 1) {  //不存在有组,无需合并,直接终止
                    break;
                }

                //然后找到右组,范围[M+1,R]
                int R = Math.min(M + step, len - 1);  //右组长度可能不足step

                //将两个有序数组,合并成一个整体有序数组
                merge(arr, L, M, R);

                //继续寻找下一对左、右组
                L = R + 1;
            }

            //提前校验步长大小,避免溢出
            if (step >= len / 2) {
                break;
            }

            //步长每次*2
            step = step << 1;
        }
    }

    /**
     * 合并操作
     * 将arr[L,M]和arr[M+1,R]这两个有序数组,合并成一个整体有序的数组
     */
    public static void merge(int[] arr, int L, int M, int R) {
        //创建临时数组
        int len = R - L + 1;
        int[] tmp = new int[len];

        //初始化索引
        int l = L;
        int r = M + 1;
        int i = 0;

        //同时遍历两个有序数组,将较小的元素拷贝到临时数组中,并移动对应的索引
        while (l <= M && r <= R) {
            if (arr[l] <= arr[r]) {
                tmp[i++] = arr[l++];
            } else {
                tmp[i++] = arr[r++];
            }
        }

        //当其中一个数组已经遍历结束后,直接拷贝另一个数组
        while (l <= M) {
            tmp[i++] = arr[l++];
        }
        while (r <= R) {
            tmp[i++] = arr[r++];
        }

        //最后将临时数组拷贝回原数组
        for (i = 0; i < len; i++) {
            arr[L + i] = tmp[i];
        }
    }
}
